import 'dart:core';
import 'dart:math';
import 'dart:ui' as ui;

import 'package:flutter/cupertino.dart';
import 'package:flutter/material.dart';

///四叉树学习
///https://blog.csdn.net/u013052238/article/details/118889232
///https://davidhsu666.com/archives/quadtree_in_2d/
///https://blog.csdn.net/MaxLykoS/article/details/108910953?utm_medium=distribute.pc_relevant.none-task-blog-baidujs_title-0&spm=1001.2101.3001.4242
///
class QuadtreeLearningWidget2 extends StatefulWidget {
  @override
  _QuadtreeLearningWidget2State createState() =>
      _QuadtreeLearningWidget2State();
}

class _QuadtreeLearningWidget2State extends State<QuadtreeLearningWidget2>
    with SingleTickerProviderStateMixin {
  Quadtree? quadtree =
      Quadtree(0, -1, Rect.fromLTRB(0, 0, 800, 800), <FNode>[], <Quadtree>[]);

  List<Flink> links = <Flink>[];
  List<FNode> nodes = <FNode>[];

  double radius = 20;

  @override
  void initState() {
    super.initState();
    initializeNodes();
  }

  void initializeNodes() {
    var initialRadius = 100;
    var initialAngle = 0.8;
    // var initialAngle = pi*(3-sqrt(5));

    print("initialAngle:$initialAngle");
    print("sqrt(5):${sqrt(5)}");
    print("pi:${pi}");
    print(" cos(10):${cos(10)}");

    List<FNode> initOffset = <FNode>[];
    List<double> listX = <double>[];
    List<double> listY = <double>[];

    //偏移
    double transplant = 400;
    for (int i = 0; i < 15; i++) {
      var radius = (initialRadius * sqrt(i));
      var angle = i * initialAngle;
      var offset = Node(transplant * 2 + radius * cos(angle),
          transplant + radius * sin(angle));
      listX.add(offset.dx);
      listY.add(offset.dy);
      print("初始化:${offset.toString()}");

      var fnode = FNode(offset, offset, offset, i);
      initOffset.add(fnode);

      nodes.add(fnode);
    }

    double xMin = listX.reduce(min);
    double xMax = listX.reduce(max);

    double yMin = listY.reduce(min);
    double yMax = listY.reduce(max);

    print("xMin:$xMin---xMax$xMax---yMin:$yMin---yMax$yMax");

    //xMin-1，这些防止点在线上，rect.contains 没算进去
    quadtree = Quadtree(
        0,
        -1,
        Rect.fromLTRB(xMin - 1, yMin - 1, xMax + 1, yMax + 1),
        <FNode>[],
        <Quadtree>[]);
    for (FNode offset in initOffset) {
      quadtree?.insert(quadtree!, offset);
    }

    createLink(0, 10);
    // createLink(0, 12);
    // createLink(1, 5);
    // createLink(3, 6);
    // createLink(7, 8);
    // createLink(5, 3);
    // createLink(5, 10);
    // createLink(3, 10);
    resetInsertPoint(nodes);
    for (int i = 0; i < 10; i++) {
      // tick3();
      tick4();

    }
    // tick2();

    for (FNode offset in quadtree!
        .queryRectPoint(quadtree!, Rect.fromLTRB(400, 339.6, 800, 500))) {
      print("查询区域点${offset.sourcePoint.toString()}");
    }
  }

  double alpha = 0.2;
  double gravity = 0.2;
  double width = 2 * 20;
  double height = 2 * 20;
  double strength = 0.7;
  double distance = 150;
  double friction = 0.8;
  double charge = -200;

  var _time = 0;

  void tick() {
    _time++;
    if ((alpha *= 0.99) < 0.005) {
      // Log.e("Force", "time="+_time);
      return;
    }

    // for (int pointIndex = 0; pointIndex < nodes.length; pointIndex++) {
    //   int value = Random().nextInt(nodes.length);
    //   links.add(Flink(LinkNode(nodes[pointIndex].sourcePoint, pointIndex + 1),
    //       LinkNode(nodes[value].targetPoint, pointIndex + 1)));
    //   nodes[pointIndex] = FNode(
    //       links[pointIndex].source.point, links[pointIndex].target.point, links[pointIndex].target.point, 0);
    // }

    if (nodes == null || links == null) {
      return;
    }

    final int nodeCount = nodes.length;
    int linkCount = links.length;

    //拉力计算方法
    // for (int i = 0; i < linkCount; i++) {
    //   Flink link = links[i];
    //   LinkNode sourceLinkNode = link.source;
    //   LinkNode targetLinkNode = link.target;
    //
    //   Node sourceNode = sourceLinkNode.point;
    //   Node targetNode = targetLinkNode.point;
    //   double dx = targetNode.dx - sourceNode.dx;
    //   double dy = targetNode.dy - sourceNode.dy;
    //   double d = dx * dx + dy * dy;
    //   if (d > 0) {
    //     d = sqrt(d);
    //
    //     d = alpha * linkStrength() * (d - linkDistance(link)) / d;
    //     dx *= d;
    //     dy *= d;
    //
    //     double k = sourceLinkNode.weight * 1.0 / (targetLinkNode.weight + sourceLinkNode.weight);
    //     targetNode.dx -= dx * k;
    //     targetNode.dy -= dy * k;
    //
    //     // k = 1 - k;
    //     sourceNode.dx += dx * k;
    //     sourceNode.dy += dy * k;
    //   }
    // }
    //
    // //聚力计算方法，让整个分布趋于椭圆
    // double k = alpha * gravity;
    // double k2 =  alpha * (gravity + 0.05);
    // if (k != 0) {
    //   double w = width / 2;
    //   double h = height / 2;
    //   for (int i = 0; i < nodeCount; i++) {
    //     Node node = nodes[i].sourcePoint;
    //     node.dx += (w - node.dx) * k;
    //     node.dy += (h - node.dy) * k2;
    //
    //   }
    // }
    //
    // //排斥力计算，使用四叉树让减少计算，提高效率
    // if (charge != 0) {
    //   final QuadTree quadTree = getQuadTree(nodes);
    //   forceAccumulate(quadTree.root);
    //   for (int i = 0; i < nodeCount; i++) {
    //     final FNode node = nodes.get(i);
    //     if (!node.isStable()) {
    //       visitQuadTree(quadTree.root, node, minX, minY, maxX, maxY);
    //     }
    //   }
    // }
    //
    // for (int i = 0; i < nodeCount; i++) {
    //   FNode node = nodes[i];
    //   if (false) {
    //     node.sourcePoint.dx = node.lastPoint.dx;
    //     node.sourcePoint.dy = node.lastPoint.dy;
    //   } else {
    //     node.sourcePoint.dx -= (node.lastPoint.dx - (node.lastPoint.dx = node.sourcePoint.dx)) * friction;
    //     node.sourcePoint.dy -= (node.lastPoint.dy - (node.lastPoint.dy = node.sourcePoint.dy)) * friction;
    //   }
    // }
    resetInsertPoint(nodes);
  }

  void tick3() {
    _time++;
    if ((alpha *= 0.99) < 0.005) {
      // Log.e("Force", "time="+_time);
      return;
    }

    if (nodes == null || links == null) {
      return;
    }

    final int nodeCount = nodes.length;
    int linkCount = links.length;

    //拉力计算方法
    for (int i = 0; i < nodeCount; i++) {
      FNode link = nodes[i];
      if (link.sourcePoint.dx == link.targetPoint.dx &&
          link.sourcePoint.dy == link.targetPoint.dy) {
        print("自身");
        continue;
      }
      Node sourceNode = link.sourcePoint;
      Node targetNode = link.targetPoint;
      double dx = targetNode.dx - sourceNode.dx;
      double dy = targetNode.dy - sourceNode.dy;
      double d = dx * dx + dy * dy;
      double sqrtD = sqrt(d);
      Rect rect1 = Rect.fromPoints(Offset(sourceNode.dx, sourceNode.dy),
          Offset(targetNode.dx, targetNode.dy));
      var rect = Rect.fromLTRB(
          rect1.left, rect1.top , rect1.right , rect1.bottom );
       rect = Rect.fromLTRB(
        sourceNode.dx-sqrtD, sourceNode.dy-sqrtD ,    sourceNode.dx+sqrtD, sourceNode.dy+sqrtD);

      List<FNode> rectPoints = quadtree!.queryRectPoint(quadtree!, rect);

        for (FNode rectPoint in rectPoints) {
          var rectTargetPointNode = rectPoint.targetPoint;
          var rectSourcePointNode = rectPoint.sourcePoint;
          //当前区域的点，没有其他线相连
          if (rectPoint.targetPoint.dx == rectPoint.sourcePoint.dx &&
              rectPoint.targetPoint.dy == rectPoint.sourcePoint.dy) {
            continue;
          }

          //相交的话
          for (int i = 0; i < 20; i++) {
            if (intersect3(sourceNode, targetNode, rectSourcePointNode,
                rectTargetPointNode)) {
              //按等比例缩放移动x，y点
              var targetendX = targetNode.dx -
                  (targetNode.dx - sourceNode.dx) * radius / sqrtD;
              var targetendY = targetNode.dy -
                  (targetNode.dy - sourceNode.dy) * radius / sqrtD;

              var sourceendX = sourceNode.dx +
                  (sourceNode.dx - targetNode.dx) * radius / sqrtD;
              var sourceendY = sourceNode.dy +
                  (sourceNode.dy - targetNode.dy) * radius / sqrtD;

              sourceNode.dx = sourceendX;
              sourceNode.dy = sourceendY;

              targetNode.dx = targetendX;
              targetNode.dy = targetendY;
            }else{
              break;
            }
          }
        }

    }
    //
    // //聚力计算方法，让整个分布趋于椭圆
    // for (int i = 0; i < 10; i++) {
    //   double k = alpha * gravity;
    //   double k2 = alpha * (gravity + 0.05);
    //   if (k != 0) {
    //     double w = width / 2;
    //     double h = height / 2;
    //     for (int i = 0; i < nodeCount; i++) {
    //       Node node = nodes[i].sourcePoint;
    //       node.dx += (w - node.dx) * k;
    //       node.dy += (h - node.dy) * k2;
    //     }
    //   }
    // }
    //
    // //排斥力计算，使用四叉树让减少计算，提高效率
    // if (charge != 0) {
    //   final QuadTree quadTree = getQuadTree(nodes);
    //   forceAccumulate(quadTree.root);
    //   for (int i = 0; i < nodeCount; i++) {
    //     final FNode node = nodes.get(i);
    //     if (!node.isStable()) {
    //       visitQuadTree(quadTree.root, node, minX, minY, maxX, maxY);
    //     }
    //   }
    // }
    //
    // for (int i = 0; i < nodeCount; i++) {
    //   FNode node = nodes[i];
    //   if (false) {
    //     node.sourcePoint.dx = node.lastPoint.dx;
    //     node.sourcePoint.dy = node.lastPoint.dy;
    //   } else {
    //     node.sourcePoint.dx -= (node.lastPoint.dx - (node.lastPoint.dx = node.sourcePoint.dx)) * friction;
    //     node.sourcePoint.dy -= (node.lastPoint.dy - (node.lastPoint.dy = node.sourcePoint.dy)) * friction;
    //   }
    // }
    // resetInsertPoint(nodes);
  }
  double determinant(double v1, double v2, double v3, double v4)  // 行列式
  {
    return (v1*v3-v2*v4);
  }
  bool intersect3(Node aa, Node bb, Node cc, Node dd)
  {
    double delta = determinant(bb.dx-aa.dx,dd.dx-cc.dx, dd.dy-cc.dy, bb.dy-aa.dy);
    if ( delta<=(1e-6) && delta>=-(1e-6) )  // delta=0，表示两线段重合或平行
        {
      return false;
    }
    double namenda = determinant(dd.dx-cc.dx, aa.dx-cc.dx, aa.dy-cc.dy, dd.dy-cc.dy) / delta;
    if ( namenda>1 || namenda<0 )
    {
      return false;
    }
    double miu = determinant(bb.dx-aa.dx, aa.dx-cc.dx, aa.dy-cc.dy, bb.dy-aa.dy) / delta;
    if ( miu>1 || miu<0 )
    {
      return false;
    }
    return true;
  }
  void createLink(int source, int target) {
    var flink = Flink(LinkNode(nodes[source].sourcePoint, source + 1),
        LinkNode(nodes[target].sourcePoint, source + 1));
    links.add(flink);
    nodes[source] = FNode(
        flink.source.point, flink.target.point, flink.target.point, source);
  }

  void tick4() {
    _time++;
    if ((alpha *= 0.99) < 0.005) {
      // Log.e("Force", "time="+_time);
      return;
    }

    if (nodes == null || links == null) {
      return;
    }

    final int nodeCount = nodes.length;
    int linkCount = links.length;

    //拉力计算方法
    for (int i = 0; i < nodeCount; i++) {
      FNode link = nodes[i];
      if (link.sourcePoint.dx == link.targetPoint.dx &&
          link.sourcePoint.dy == link.targetPoint.dy) {
        print("自身");
        continue;
      }
      Node sourceNode = link.sourcePoint;
      Node targetNode = link.targetPoint;
      double dx = targetNode.dx - sourceNode.dx;
      double dy = targetNode.dy - sourceNode.dy;
      double d = dx * dx + dy * dy;
      double sqrtD = sqrt(d);
      Rect rect1 = Rect.fromPoints(Offset(sourceNode.dx, sourceNode.dy),
          Offset(targetNode.dx, targetNode.dy));
      var rect = Rect.fromLTRB(
          rect1.left, rect1.top , rect1.right , rect1.bottom );

      rect= Rect.fromLTRB(
          rect1.left-radius, rect1.top-radius , rect1.right+radius , rect1.bottom +radius);

      List<FNode> rectPoints = quadtree!.queryRectPoint(quadtree!, rect);

      for (FNode rectPoint in rectPoints) {
        var rectSourcePointNode = rectPoint.sourcePoint;
        var rectTargetPointNode = rectPoint.targetPoint;



        Rect rectOther = Rect.fromPoints(Offset(rectSourcePointNode.dx, rectSourcePointNode.dy),
            Offset(rectTargetPointNode.dx, rectTargetPointNode.dy));
        rectOther =  Rect.fromLTRB(
            rectOther.left-radius, rectOther.top-radius , rectOther.right , rectOther.bottom );


        //矩形相交
          if (!(rect.left + rect.width < rectOther.left||rect.top + rect.height < rectOther.top||
              rectOther.left + rectOther.width < rect.left||  rectOther.top + rectOther.height < rect.top
          ) ) {
            //当前区域的点，没有其他线相连
            if (rectPoint.targetPoint.dx == rectPoint.sourcePoint.dx &&
                rectPoint.targetPoint.dy == rectPoint.sourcePoint.dy) {

              continue;
            }

            //按等比例缩放移动x，y点
            // var targetendX = targetNode.dx -
            //     (targetNode.dx - sourceNode.dx) * radius / sqrtD;
            // var targetendY = targetNode.dy -
            //     (targetNode.dy - sourceNode.dy) * radius / sqrtD;

            double rad = (Offset(sourceNode.dx, sourceNode.dy)-Offset(targetNode.dx, targetNode.dy)).direction;
            rad =  rad < 0 ? 2 * pi + rad : rad;
            var targetendX = targetNode.dx + radius*cos(rad);
            var targetendY = targetNode.dy + radius*sin(rad);

            var sourceendX = sourceNode.dx + radius*cos(rad);
            var sourceendY = sourceNode.dy + radius*sin(rad);

            // var sourceendX = sourceNode.dx +
            //     (sourceNode.dx - targetNode.dx) * radius / sqrtD;
            // var sourceendY = sourceNode.dy +
            //     (sourceNode.dy - targetNode.dy) * radius / sqrtD;
            //
            sourceNode.dx = sourceendX;
            sourceNode.dy = sourceendY;

            targetNode.dx = targetendX;
            targetNode.dy = targetendY;
          }

      }

    }
    //
    // //聚力计算方法，让整个分布趋于椭圆
    for (int i = 0; i < 1; i++) {
      double k = alpha * gravity;
      double k2 = alpha * (gravity + 0.05);
      if (k != 0) {
        double w = width / 2;
        double h = height / 2;
        for (int i = 0; i < nodeCount; i++) {
          Node node = nodes[i].sourcePoint;
          node.dx += (w - node.dx) * k;
          node.dy += (h - node.dy) * k2;
        }
      }
    }
    //
    // //排斥力计算，使用四叉树让减少计算，提高效率
    // if (charge != 0) {
    //   final QuadTree quadTree = getQuadTree(nodes);
    //   forceAccumulate(quadTree.root);
    //   for (int i = 0; i < nodeCount; i++) {
    //     final FNode node = nodes.get(i);
    //     if (!node.isStable()) {
    //       visitQuadTree(quadTree.root, node, minX, minY, maxX, maxY);
    //     }
    //   }
    // }
    //
    // for (int i = 0; i < nodeCount; i++) {
    //   FNode node = nodes[i];
    //   if (false) {
    //     node.sourcePoint.dx = node.lastPoint.dx;
    //     node.sourcePoint.dy = node.lastPoint.dy;
    //   } else {
    //     node.sourcePoint.dx -= (node.lastPoint.dx - (node.lastPoint.dx = node.sourcePoint.dx)) * friction;
    //     node.sourcePoint.dy -= (node.lastPoint.dy - (node.lastPoint.dy = node.sourcePoint.dy)) * friction;
    //   }
    // }
    // resetInsertPoint(nodes);
  }


  void tick2() {
    _time++;
    if ((alpha *= 0.99) < 0.005) {
      // Log.e("Force", "time="+_time);
      return;
    }

    //随机模拟牵连关系

    // links.add(Flink(LinkNode(nodes[0].sourcePoint, 0 + 1),
    //     LinkNode(nodes[10].sourcePoint, 0 + 1)));
    // nodes[0] = FNode(
    //     links[0].source.point, links[0].target.point, links[0].target.point, 0);
    for (int pointIndex = 0; pointIndex < nodes.length; pointIndex++) {
      int value = Random().nextInt(nodes.length);
      links.add(Flink(LinkNode(nodes[pointIndex].sourcePoint, pointIndex + 1),
          LinkNode(nodes[value].targetPoint, pointIndex + 1)));
      nodes[pointIndex] = FNode(links[pointIndex].source.point,
          links[pointIndex].target.point, links[pointIndex].target.point, 0);
    }

    if (nodes == null || links == null) {
      return;
    }

    final int nodeCount = nodes.length;
    int linkCount = links.length;

    //拉力计算方法
    for (int i = 0; i < linkCount; i++) {
      Flink link = links[i];
      LinkNode sourceLinkNode = link.source;
      LinkNode targetLinkNode = link.target;

      Node sourceNode = sourceLinkNode.point;
      Node targetNode = targetLinkNode.point;
      double dx = targetNode.dx - sourceNode.dx;
      double dy = targetNode.dy - sourceNode.dy;
      double d = dx * dx + dy * dy;

      Rect rect1 = Rect.fromPoints(Offset(sourceNode.dx, sourceNode.dy),
          Offset(targetNode.dx, targetNode.dy));
      var rect = Rect.fromLTRB(
          rect1.left - 1, rect1.top - 1, rect1.right + 1, rect1.bottom + 1);

      List<FNode> rectPoints = quadtree!.queryRectPoint(quadtree!, rect);
      if (rectPoints.length >= 2) {
        double sqrtD = sqrt(d);

        for (FNode rectPoint in rectPoints) {
          if (rectPoint.sourcePoint.dx == targetNode.dx &&
              rectPoint.sourcePoint.dy == targetNode.dy) {
            var endX = targetNode.dx -
                (targetNode.dx - sourceNode.dx) *
                    (((sqrtD - 2 * radius) / 2) + radius) /
                    sqrtD;
            var endY = targetNode.dy -
                (targetNode.dy - sourceNode.dy) *
                    (((sqrtD - 2 * radius) / 2) + radius) /
                    sqrtD;

            var lastTargetNode = Node(targetNode.dx, targetNode.dy);
            targetNode.dx = endX;
            targetNode.dy = endY;
            var node = nodes[i];
            nodes[i] = FNode(
                node.sourcePoint, targetNode, lastTargetNode, node.nodeIndex);
          } else if (rectPoint.sourcePoint.dx != sourceNode.dx &&
              rectPoint.sourcePoint.dy != sourceNode.dy) {
            ///rectPoint.sourcePoint 对应两点间的目标点
            double dx = rectPoint.sourcePoint.dx - sourceNode.dx;
            double dy = rectPoint.sourcePoint.dy - sourceNode.dy;

            double sqrtOther = sqrt(dx * dx + dy * dy);
            var endX = rectPoint.sourcePoint.dx -
                (rectPoint.sourcePoint.dx - sourceNode.dx) *
                    -(sqrtOther + radius) /
                    sqrtOther;
            var endY = rectPoint.sourcePoint.dy -
                (rectPoint.sourcePoint.dy - sourceNode.dy) *
                    -(sqrtOther + radius) /
                    sqrtOther;
            var lastTargetNode =
                Node(rectPoint.sourcePoint.dx, rectPoint.sourcePoint.dy);

            var node = nodes[rectPoint.nodeIndex];
            nodes[rectPoint.nodeIndex].sourcePoint = Node(endX, endY);
            // FNode(
            //    Node(endX,endY), rectPoint.targetPoint, lastTargetNode, node.nodeIndex);
            //
            // //线
            // // links[rectPoint.nodeIndex].source.point =  Node(endX,endY);
            // for (Flink linePoint in links) {
            //   if(linePoint.target.point.dx == lastTargetNode.dx && linePoint.target.point.dy == lastTargetNode.dy){
            //     linePoint.target.point = Node(endX,endY);
            //   }
            // }
          }
        }
      }
    }

    resetInsertPoint(nodes);
  }

  ///计算好 树之间的距离关系后 重新构建
  void resetInsertPoint(List<FNode> nodes) {
    List<FNode> initOffset = <FNode>[];
    List<double> listX = <double>[];
    List<double> listY = <double>[];

    // links.clear();
    for (int i = 0; i < nodes.length; i++) {
      listX.add(nodes[i].sourcePoint.dx);
      listY.add(nodes[i].sourcePoint.dy);
      initOffset.add(nodes[i]);

      // links.add(Flink(LinkNode(nodes[i].sourcePoint, i + 1),
      //     LinkNode(nodes[i].targetPoint, i + 1)));
    }
    double xMin = listX.reduce(min);
    double xMax = listX.reduce(max);
    double yMin = listY.reduce(min);
    double yMax = listY.reduce(max);

    print("xMin:$xMin---xMax$xMax---yMin:$yMin---yMax$yMax");

    //xMin-1，这些防止点在线上，rect.contains 没算进去
    quadtree = null;
    quadtree = Quadtree(
        0,
        -1,
        Rect.fromLTRB(xMin - 1, yMin - 1, xMax + 1, yMax + 1),
        <FNode>[],
        <Quadtree>[]);

    for (FNode offset in initOffset) {
      quadtree!.insert(quadtree!, offset);
    }
  }

  linkStrength() {
    double k = 1;
    return strength * k;
  }

  double linkDistance(Flink link) {
    return distance + radius + radius;
  }

  @override
  Widget build(BuildContext context) {
    return Material(
      child: Center(
          child: Container(
        child: Listener(
          onPointerDown: (details) {
            // var offset =
            //     Offset(details.localPosition.dx, details.localPosition.dy);
            // quadtree.insert(quadtree, offset);
            // print("点击：${offset.toString()}");
            // setState(() {});
          },
          child: Container(
            width: double.infinity,
            height: double.infinity,
            color: Color(0xffffffff),
            child: RepaintBoundary(
              //隔离重绘控件，singlescrollview 滑动发生重绘，导致画笔paint响应
              child: CustomPaint(
                painter: _CirclePainter(quadtree: quadtree!, links: links),
              ),
            ),
          ),
        ),
      )),
    );
  }

  @override
  void dispose() {
    super.dispose();
  }
}

class _CirclePainter extends CustomPainter {
  Quadtree quadtree;
  List<Flink> links;

  _CirclePainter({required this.quadtree, required this.links});

  double radius = 20;

  @override
  void paint(Canvas canvas, Size size) {
    Paint _painter = Paint()
      ..color = Color(0xFF00FDF4)
      ..style = PaintingStyle.fill
      ..isAntiAlias = true;

    Paint _painterLine = Paint()
      ..color = Color(0xFFF50000)
      ..style = PaintingStyle.stroke
      ..isAntiAlias = true;

    Paint _painterTowLine = Paint()
      ..color = Color(0xFF000000)
      ..style = PaintingStyle.stroke
      ..isAntiAlias = true;

    // if(quadtree.nodes != null && quadtree.nodes.length==0){
    //   drawPath(quadtree, canvas, _painterLine);
    // }else{
    //   for (Quadtree quadtreeChild in quadtree.nodes) {
    //     drawPath(quadtreeChild, canvas, _painterLine);
    //   }
    // }
    var quadtreeList = quadtree.queryPathPoint(quadtree);

    //点十字架的象限域划分
    for (int i = 0; i < quadtreeList.length; i++) {
      var child = quadtreeList[i];
      if (child.currentLevel == 1) {
        _painterLine..color = Color(0xFFECC817);
      } else if (child.currentLevel == 2) {
        _painterLine..color = Color(0xFF68F103);
      } else if (child.currentLevel == 3) {
        _painterLine..color = Color(0xFF00E5DB);
      } else if (child.currentLevel == 4) {
        _painterLine..color = Color(0xFF0712F8);
      }
      drawPath(quadtreeList[i], canvas, _painterLine);
    }

    //每个点
    drawPoint(quadtree, canvas, _painter);

    //两点连线
    drawTwoPointPath(canvas, _painterTowLine);
  }

  // void drawPoint(Quadtree quadtree, ui.Canvas canvas, ui.Paint _painter) {
  //   for(Offset point in quadtree.queryPoint(quadtree)){
  //     print("drawPoint：${point.toString()}");
  //     canvas.drawCircle(
  //         point, 4, _painter);
  //   }
  //
  // }
  void drawPoint(Quadtree quadtree, ui.Canvas canvas, ui.Paint _painter) {
    for (PointColor pointColor in quadtree.queryPoint(quadtree)) {
      _painter.color = pointColor.color;
      for (FNode point in pointColor.offset) {
        // print("drawPoint：${point.toString()}");
        canvas.drawCircle(Offset(point.sourcePoint.dx, point.sourcePoint.dy),
            radius, _painter);
      }
    }
  }

  void drawPath(Quadtree quadtree, ui.Canvas canvas, ui.Paint _painterLine) {
    if (quadtree.rectangle != null &&
        quadtree.nodes != null &&
        quadtree.nodes.length == 4) {
      var path = Path();

      print("${quadtree.rectangle.left}---${quadtree.point.dy}");
      print("${quadtree.rectangle.right}---${quadtree.point.dy}");

      var startX = quadtree.rectangle.left;
      var startY = quadtree.point.dy;
      var endX = quadtree.rectangle.right;
      var endY = quadtree.point.dy;

      path.moveTo(startX, startY);
      path.lineTo(endX, endY);
      path.moveTo(quadtree.point.dx, quadtree.rectangle.top);
      path.lineTo(quadtree.point.dx, quadtree.rectangle.bottom);
      canvas.drawPath(path, _painterLine);
    }
  }

  void drawTwoPointPath(ui.Canvas canvas, ui.Paint _painterLine) {
    for (var link in links) {
      var p00 = link.source.point;
      var p03 = link.target.point;

      double distanceX = 0;
      double distanceY = 0;

      //取两圆x，y长度
      distanceY = (p03.dy - p00.dy).abs();
      distanceX = (p03.dx - p00.dx).abs();

      double twoPointDistance =
          sqrt(distanceY * distanceY + distanceX * distanceX);
      //目标点
      double endX = 0;
      double endY = 0;

      //按等比例缩放移动x，y点
      endX = p03.dx - (p03.dx - p00.dx) * radius / twoPointDistance;
      endY = p03.dy - (p03.dy - p00.dy) * radius / twoPointDistance;

      double centerX = (p00.dx + endX) / 2;
      double centerY = (p00.dy + endY) / 2;

      double lenX = (endX - p00.dx);
      double lenY = (endY - p00.dy);
      double lenXY = sqrt((lenX * lenX + lenY * lenY));

      print("object:radian lenXY 角度--:${acos(lenX / lenXY)}---");

      //得出弧度，lenX / lenXY 为出发点圆夹角
      double radian = acos(lenX / lenXY) * (p00.dy < p03.dy ? 1 : -1);

      //得出，半圆为Π，得出补角弧度，pi / 2-radian
      double centerRadian = pi / 2 - radian;
      double tempAssX = (centerX + lenXY / 4 * cos(centerRadian));
      double tempAssY = (centerY - lenXY / 4 * sin(centerRadian));

      //计算两边的箭头点，比例是试出来的
      double arrowAssX = (centerX + lenXY * cos(centerRadian));
      double arrowAssY = (centerY - lenXY * sin(centerRadian));
      double arrowAssX2 = (centerX - lenXY / 3 * cos(centerRadian));
      double arrowAssY2 = (centerY + lenXY / 3 * sin(centerRadian));

      var path = Path();
      path.moveTo(p00.dx, p00.dy);

      path.quadraticBezierTo(tempAssX, tempAssY, endX, endY);
      // path.lineTo(endX,endY);
      canvas.drawPath(path, _painterLine);

      //画箭头,
      drawArrow(canvas, centerX, centerY, arrowAssX, arrowAssY, endX, endY,
          arrowAssX2, arrowAssY2);

      //中心点
      Paint _painterLine1 = Paint()
        ..color = Color(0xFFFFFFFF)
        ..style = PaintingStyle.fill
        ..isAntiAlias = true;
      canvas.drawCircle(Offset(centerX, centerY), 2, _painterLine1);

      //控制心点
      Paint _painterLine2 = Paint()
        ..color = Color(0xFFFFA100)
        ..style = PaintingStyle.fill
        ..isAntiAlias = true;
      canvas.drawCircle(Offset(tempAssX, tempAssY), 2, _painterLine2);
    }
  }

  void drawArrow(
    Canvas canvas,
    double centerX,
    double centerY,
    double controlX,
    double controlY,
    double endX,
    double endY,
    double controlX2,
    double controlY2,
  ) {
    Paint _painterArrow = Paint()
      ..color = Color(0xFFF50000)
      ..style = PaintingStyle.stroke
      ..isAntiAlias = true;
    var pathArrow = Path();

    double controlEndDistance = sqrt((endX - controlX) * (endX - controlX) +
        (endY - controlY) * (endY - controlY));

    //进行比例缩放得出箭头点
    double lineToX = endX - (endX - controlX) * 10 / controlEndDistance;
    double lineToY = endY - (endY - controlY) * 10 / controlEndDistance;

    double lineToX2 = endX - (endX - controlX2) * 18 / controlEndDistance;
    double lineToY2 = endY - (endY - controlY2) * 18 / controlEndDistance;

    pathArrow.moveTo(endX, endY);
    pathArrow.lineTo(lineToX, lineToY);
    pathArrow.moveTo(endX, endY);
    pathArrow.lineTo(lineToX2, lineToY2);
    canvas.drawPath(pathArrow, _painterArrow);
  }

  @override
  bool shouldRepaint(covariant CustomPainter oldDelegate) {
    return true;
  }
}

class Quadtree {
  int MAX_OBJECTS = 4;
  int MAX_LEVELS = 3;

  //当前等级
  int currentLevel;

  //当前父等级
  int currentPLevel;

  //区域
  Rect rectangle;

  List<Rect> childRects = <Rect>[];

  //该区域容器的物体集合
  List<FNode> objects;

  //中节点位置
  Offset point = Offset(-1, -1);

  //当前象限下 只能有4个
  List<Quadtree> nodes;

  late Quadtree quadtree;

  Quadtree(this.currentLevel, this.currentPLevel, this.rectangle, this.objects,
      this.nodes) {
    point = Offset(rectangle.left + (rectangle.right - rectangle.left) / 2,
        rectangle.top + (rectangle.bottom - rectangle.top) / 2);
  }

  void init() {
    quadtree =
        Quadtree(0, -1, Rect.fromLTRB(0, 0, 800, 800), <FNode>[], <Quadtree>[]);
  }

  void insert(Quadtree quadtree, FNode point) {
    if (!quadtree.rectangle
        .contains(Offset(point.sourcePoint.dx, point.sourcePoint.dy))) {
      return;
    }

    if (quadtree.currentLevel > MAX_LEVELS) {
      return;
    }

    if (quadtree.objects.length < MAX_OBJECTS) {
      quadtree.objects.add(point);
      return;
    }

    if (quadtree.nodes != null && quadtree.nodes.length == 0) {
      spitRect(quadtree, point);
    } else {
      for (Quadtree quadtreeChild in quadtree.nodes) {
        quadtreeChild.insert(quadtreeChild, point);
      }
    }
  }

  void spitRect(Quadtree quadtree, FNode point) {
    for (int index = 0; index < 4; index++) {
      if (index == 0) {
        Quadtree quadChild = Quadtree(
            quadtree.currentLevel + 1,
            quadtree.currentPLevel + 1,
            Rect.fromLTRB(quadtree.rectangle.left, quadtree.rectangle.top,
                quadtree.point.dx, quadtree.point.dy),
            <FNode>[],
            <Quadtree>[]);
        quadtree.nodes.add(quadChild);
      }
      if (index == 1) {
        Quadtree quadChild = Quadtree(
            quadtree.currentLevel + 1,
            quadtree.currentPLevel + 1,
            Rect.fromLTRB(quadtree.point.dx, quadtree.rectangle.top,
                quadtree.rectangle.right, quadtree.point.dy),
            <FNode>[],
            <Quadtree>[]);
        quadtree.nodes.add(quadChild);
      }

      if (index == 2) {
        Quadtree quadChild = Quadtree(
            quadtree.currentLevel + 1,
            quadtree.currentPLevel + 1,
            Rect.fromLTRB(quadtree.point.dx, quadtree.point.dy,
                quadtree.rectangle.right, quadtree.rectangle.bottom),
            <FNode>[],
            <Quadtree>[]);
        quadtree.nodes.add(quadChild);
      }

      if (index == 3) {
        Quadtree quadChild = Quadtree(
            quadtree.currentLevel + 1,
            quadtree.currentPLevel + 1,
            Rect.fromLTRB(quadtree.rectangle.left, quadtree.point.dy,
                quadtree.point.dx, quadtree.rectangle.bottom),
            <FNode>[],
            <Quadtree>[]);
        quadtree.nodes.add(quadChild);
      }
      //继续插入
      insert(quadtree.nodes[index], point);
    }
  }

  ///查询所有的点
  List<FNode> queryAllPoint(Quadtree quadtree) {
    List<FNode> points = <FNode>[];
    points.addAll(quadtree.objects);
    if (quadtree.nodes != null) {
      for (Quadtree child in quadtree.nodes) {
        points.addAll(queryAllPoint(child));
      }
    }
    return points;
  }

  ///为不同等级的象限点添加颜色区分
  List<PointColor> queryPoint(Quadtree quadtree) {
    List<PointColor> points = <PointColor>[];
    Color color = Color(0xFFEF0606);
    if (quadtree.currentLevel == 1) {
      color = Color(0xFFECC817);
    } else if (quadtree.currentLevel == 2) {
      color = Color(0xFF68F103);
    } else if (quadtree.currentLevel == 3) {
      color = Color(0xFF00E5DB);
    } else if (quadtree.currentLevel == 4) {
      color = Color(0xFF0712F8);
    }
    points.add(new PointColor(quadtree.objects, color));

    if (quadtree.nodes != null) {
      for (Quadtree child in quadtree.nodes) {
        points.addAll(queryPoint(child));
      }
    }
    return points;
  }

  List<Quadtree> queryPathPoint(Quadtree quadtree) {
    List<Quadtree> quadtrees = <Quadtree>[];
    quadtrees.add(quadtree);
    if (quadtree.nodes != null) {
      for (Quadtree child in quadtree.nodes) {
        quadtrees.addAll(queryPathPoint(child));
      }
    }
    return quadtrees;
  }

  ///查询区域中的所有点
  List<FNode> queryRectPoint(Quadtree quadtree, Rect rect) {
    List<FNode> pointRect = <FNode>[];
    Rect intersect = rect.intersect(quadtree.rectangle);
    if (intersect.right - intersect.left < 0 ||
        intersect.bottom - intersect.top < 0) {
      return pointRect;
    } else {
      //查询树中该区域的的所有点是否在在区域中
      for (FNode point in quadtree.objects) {
        if (rect.contains(Offset(point.sourcePoint.dx, point.sourcePoint.dy))) {
          pointRect.add(point);
        }
      }
      for (Quadtree child in quadtree.nodes) {
        pointRect.addAll(queryRectPoint(child, rect));
      }
    }
    return pointRect;
  }
}

class PointColor {
  List<FNode> offset;
  Color color;

  PointColor(this.offset, this.color);
}

class Flink {
  LinkNode source;
  LinkNode target;

  Flink(this.source, this.target);
}

class LinkNode {
  Node point;
  double weight;

  LinkNode(this.point, this.weight);
}

class FNode {
  Node sourcePoint;
  Node targetPoint;
  Node lastPoint;

  int nodeIndex;

  FNode(this.sourcePoint, this.targetPoint, this.lastPoint, this.nodeIndex);
}

class Node {
  double dx;
  double dy;

  Node(this.dx, this.dy);
}
